#include "BinaryTree.h"

BinaryTree::BinaryTree()
{
    root = nullptr; // 初始化为空树
}

void BinaryTree::Insert(const ElementType &element)
{
    root = InsertNode(root, element);
}

void BinaryTree::Remove(const ElementType &element)
{
    root = RemoveNode(root, element);
}

BinaryTree::ElementType *BinaryTree::FindByElement(const ElementType &element)
{
    return FindNode(root, element);
}

void BinaryTree::show()
{
    std::cout << "前序遍历:" << " ";
    PrevTree(root);
    std::cout << std::endl;
    std::cout << "中序遍历:" << " ";
    MidTree(root);
    std::cout << std::endl;
    std::cout << "后序遍历:" << " ";
    PostTree(root);
    std::cout << std::endl;
    std::cout << "层序遍历:" << " ";
    HeightTravel();
}

BinaryTree::Node *BinaryTree::InsertNode(Node *node, const ElementType &element)
{
    // 找到要插入的位置了
    if (node == nullptr)
        return new Node(element);
    // 要插入的元素已经存在  二叉排序树不放置相同数据
    if (node->data == element)
        return node;
    if (node->data > element)
    {
        // 递归插入左子树
        node->left = InsertNode(node->left, element);
        if (LRDevition(node) > 1)
        {
            // 左左
            if (node->left->data > element)
            {
                // 右旋
                node = RotateRight(node);
            }
            else // 左右
            {
                node = RotateLeftRight(node);
            }
        }
    }
    else
    {
        // 递归插入右子树
        node->right = InsertNode(node->right, element);
        if (LRDevition(node) < -1)
        {
            // 右左旋
            if (node->right->data > element)
            {
                node = RotateRightLeft(node);
            }
            else // 右右旋
            {
                node = RotateLeft(node);
            }
        }
    }
    return node;
}

BinaryTree::Node *BinaryTree::RemoveNode(Node *node, const ElementType &element)
{
    if (node == nullptr)
        return nullptr;
    if (node->data < element)
    {
        node->right = RemoveNode(node->right, element);
    }
    else if (node->data > element)
    {
        node->left = RemoveNode(node->left, element);
    }
    else
    {
        // 叶子节点
        if (node->left == nullptr && node->right == nullptr)
        {
            delete node;
            return nullptr;
        }
        // 有两个孩子
        else if (node->left != nullptr && node->right != nullptr)
        {
            // 找到右子树中的最小值
            Node *minNode = GetMinNode(node->right);
            node->data = minNode->data; // 把最小值结点的数据给到要删除的结点
            // 删除右子树中的最小结点
            node->right = RemoveNode(node->right, minNode->data);
        }
        // 有一个孩子
        else
        {
            // 把我的孩子接给我的双亲节点
            Node *child = node->left ? node->left : node->right;
            delete node;
            node = child;
        }
    }
    
    if(LRDevition(node) > 1) //左边重
    {
        //左左
        if(LRDevition(node->left) >0)
        {
            node = RotateRight(node);
        }
        else  //左右 
        {
            node = RotateLeftRight(node);
        }
    }
    if(LRDevition(node) < -1) //右边重
    {
        //右右
        if(LRDevition(node->right) > 0)
        {
            node = RotateLeft(node);
        }
        else //右左
        {
            node = RotateLeftRight(node);
        }

    }
    
    return node;
}

BinaryTree::Node *BinaryTree::GetMinNode(Node *node)
{
    Node *minNode = node;
    while (node->left)
        minNode = node;
    return minNode;
}

BinaryTree::ElementType *BinaryTree::FindNode(Node *node, const ElementType &element)
{
    if (node == nullptr)
        return nullptr;
    if (node->data == element)
        return &node->data;
    else if (node->data > element)
        return FindNode(node->left, element);
    else
        return FindNode(node->right, element);
}

void BinaryTree::PrevTree(Node *node)
{
    if (node == nullptr)
        return;
    std::cout << node->data << " ";
    PrevTree(node->left);
    PrevTree(node->right);
}

void BinaryTree::MidTree(Node *node)
{
    if (node == nullptr)
        return;
    MidTree(node->left);
    std::cout << node->data << " ";
    MidTree(node->right);
}

void BinaryTree::PostTree(Node *node)
{
    if (node == nullptr)
        return;
    PostTree(node->left);
    PostTree(node->right);
    std::cout << node->data << " ";
}

void BinaryTree::HeightTravel()
{
    LinkQueue q;
    q.Push(root);
    while (!q.IsEmpty())
    {
        Node *node = (Node *)*q.GetFront();
        std::cout << node->data << " ";
        if (node->left)
            q.Push(node->left);
        if (node->right)
            q.Push(node->right);
        q.Pop();
    }
    std::cout << std::endl;
}

BinaryTree::Node *BinaryTree::RotateRight(Node *node)
{
    Node *p = node->left;
    node->left = p->right;
    p->right = node;
    return p;
}

BinaryTree::Node *BinaryTree::RotateLeft(Node *node)
{
    Node *p = node->right;
    node->right = p->left;
    p->left = node;
    return p;
}

BinaryTree::Node *BinaryTree::RotateLeftRight(Node *node)
{
    // 左子树左旋
    node->left = RotateLeft(node->left);
    return RotateRight(node); // 整体右旋
}

BinaryTree::Node *BinaryTree::RotateRightLeft(Node *node)
{
    node->right = RotateRight(node->right);
    return RotateLeft(node);
}

int BinaryTree::BinaryTree::GetNodeHeight(Node *node)
{
    if (node == nullptr)
        return 0;
    int leftHeight = GetNodeHeight(node->left);
    int rightHeight = GetNodeHeight(node->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

int BinaryTree::LRDevition(Node *node)
{
    if (node == nullptr)
        return 0;
    return GetNodeHeight(node->left) - GetNodeHeight(node->right);
}
